Aminet 7/Aminet 7 - August 1995.iso/Aminet/docs/misc/ConcNews.lha/news/amiga.programming/comp.sys.amiga.programmer_10351_000067.msg

Internet Message Format | 1994-11-27 | 7.8 KB

Path: dd.chalmers.se!news.chalmers.se!sunic!EU.net!howland.reston.ans.net!cs.utexas.edu!swrinde!sgiblab!idiom.berkeley.ca.us!apollo.west.oic.com!apollo.west.oic.com!not-for-mail
From: [e-mail] (Matthew Dillon)
Newsgroups: comp.sys.amiga.programmer
Subject: Re: How the hell does multitasking work?
Date: 5 May 1994 17:11:42 -0700
Organization: Obvious Implementations Corp
Lines: 151
Distribution: world
Message-ID: <2qc1vu$[e-mail]>
References: <[e-mail]>
NNTP-Posting-Host: apollo.west.oic.com

In article <[e-mail]> [e-mail] (Mike Austin) writes:
:I am writing down things that I would want in an operating system and
:actually making some data structures etc. when I really though about how
:pre-emptive multi-taking works.  Say you have two processes in a loop
:with equal priority.  How does exec 'let' on execute it's instructuins
:for a while then 'let' the other process have some time?  To execute an
:instruction don't you have to jump to that location?  If you did that you
:would 'become' that processs and not end until you're done...
:
:Maybe it's more like this (I am NO assembly expert)?
:
:...
:--
:                       cout << "[e-mail]" << endl;
:
:                  << I get more junk e-mail than junk mail! >>

   Well, a lot of people have answered but I figure I'll have a go at it to
   :-)

   Basically, a hardware interrupt based on a timer interrupts the currently
   running task after what is known as a time quantum.  For the sake of
   argument, lets say this quantum is 1 second.

   The processor, when it takes the interrupt, pushes the program counter and
   status register onto the stack and jumps to the interrupt handler.  The
   interrupt handler pushes all remaining registers: D0-D7,A0-A6, and saves
   the user stack pointer (A7 before the interrupt occured) in a known
   location, usually in a structure which is part of a linked list of
   tasks.

   The interrupt handler then accesses the next running task in this linked
   list and loads the stack pointer for the next task.  This stack pointer,
   of course, points to the state information for the second task.  The
   interrupt handler then pops off the registers and does a
   return-from-interrupt, which restores the status register and program
   counter FOR THE NEXT TASK.  Poof, task #2 is now running.

   The next time the interrupt occurs, the interrupt handler repeats the
   work and and on return, Poof, task #1 is running again.  The task's
   do not know or care that they are getting switched back and forth.

   Now, back to the time quantum.  If you have two tasks both in an
   infinite loop, with one printing "A" to the screen and the other printing
   "B" to the screen, you would see something like this:

       AAAAAAAAAABBBBBBBBBBAAAAAAAAAABBBBBBBBBBAAAAAAAAAABBBBBBBBBB

   (this isn't exactly what happens on the amiga since printing requires a
   task switch, but it's a good example)

   If you now reduce the time quantum down to, say, 1/10 of a second, you
   would see:

       AAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBBAAABBB

   If you now reduce the time quantum down to, say, 1/100 of a second,
   you would see:

        ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB

   Now, this isn't quite to scale, but you get the idea... the smaller the
   time quantum, the more it 'appears' from the user's perspective that the
   two tasks are running simultaniously.  Of course, there are limits... if
   you make the time quantum too small, the interrupt overhead really slows
   things down.  But anything on the order of 1/30 second will not be
   noticable in terms of overhead.

   --

   Now, part #2:  Lets say you have 10 tasks.  You want a way of telling
   the system that any given task is 'sleeping', so the system does not
   switch it in.  If you have 9 sleeping tasks and 1 running task, then
   that 1 running task gets all available CPU until one of the sleeping
   tasks wakes up.

   This sleeping/running thing can be implemented through two circular
   queues.  One queue contains a linked list of structures representing
   running tasks, and the other contains a linked list of structures
   representing sleeping tasks.  (Again, not quite the way the Amiga works,
   but good enough for argument).  When a task wants to go to sleep, it
   makes a system call that transfers it's structure form the running queue
   to the waiting queue.  When a task wants to wakeup another task (or
   an interrupt -- say, a serial interrupt to wakeup the terminal program),
   it makes a system call that places the other task back on the run queue.

   In this manner, the operating system does not waste time running tasks
   that have nothing to do at the moment.  The task switch interrupt handler
   ONLY deals with the running-tasks-queue.  Most task's are 'waiting' on
   devices.  Some random interrupt causes the device to register an event
   that one or more tasks was waiting for, resulting in the device's
   hardware interrupt routine moving the tasks in question from the wait
   queue to the run queue.

   --

   part #3:  Priorities.  Lets say you have 10 tasks and they are
   ALL running.  Each task gets about 1/10 of the CPU.  But lets say one
   of those tasks is really important and needs to be able to take more
   CPU.  By implementing a priority scheme you can give that task several
   quantums instead of just one.  In the case of the Amiga, priorities are
   fixed... the Amiga round-robins between all running tasks at the
   highest priority level and any running tasks at a lower priority level
   get no CPU at all.  This works because those higher priority tasks
   do not generally run for very long at a time... they are sleeping most
   of the time.

   In something like UNIX, priorities are more dynamic... a higher priority
   process will not completely lockout lower priority processes.

   Priorities can be implemented any number of ways... you can adjust the
   time quantum according to the priority, you can simply lock out lower
   priority tasks, or you can use a combination of the two, or do other
   things.

   --

   part #4:  Preventing screwups.  What happens when two tasks are trying
   to, say, write to the screen?   Lets say you have a common global variable
   which contains the current screen coordinates of the cursor:  x, and y.
   Task #1 read's x and y, stores the character on the screen, increments x,
   and if needs to increments y and scrolls the screen (and zero's x).

   The problem is, of course, if two tasks are doing that and the system
   switches between them, the two globals can get corrupted: task #1 reads x,
   system interrupts it and runs task #2 which also reads x (i.e. both
   tasks write to the same cursor position!), not to mention other problems.

   To handle this problem, you need some way of 'locking out' the other task
   for the duration of your little write-to-screen operation.  Most operating
   systems provide this in some manner or other... for example, a flag that
   prevents preemptive task switching.  Sophisticated operating systems
   like EXEC and UNIX allow you to selectively lockout different subsystems.

   For example, if task #1 is writing to the screen and task #2 is
   writing to the serial port, there is no particular reason to lock them
   out from each other since they both can co-exist without conflict.


   Well, that's it!

                        -Matt

--

    Matthew Dillon        [e-mail]
    1005 Apollo Way
    Incline Village, NV. 89451    ham: KC6LVW (no mail drop)
    USA             Sandel-Avery Engineering [phone]
    [always include a portion of the original email in any response!]